0%

定理1:

令$G$为一个阶数$n\geq 3$的图,如果对于任意整数$j$,满足$1\leq j < \frac{n}{2}$,$G$图中度数至多为$j$的节点个数少于$j$,那么图$G$是哈密顿图。


理解:

比较直观的理解一下就是,对于一个图,我们可以枚举$j$从$1$到$\frac{n}{2}$,比如度数至多为1的节点少于1个,度数至多为2的节点少于2个……

很容易发现,这是一个非常紧的定理,而且如果能够拿到所有节点的度的序列的话,完全可以在$O(n)$的时间复杂度下快速判断出一个图是否为哈密顿图。


前置定理:

定理:假设$u,v$是图$G$上的两个不相邻的点,但是满足$d(u)+d(v) \geq n$。那么图$G+uv$是哈密顿图当且仅当图$G$是哈密顿图。

证明:充分性是显然的。下面证明必要性:如果一个图$G+uv$是一个哈密顿图并且节点$u,v$是图上不相邻的两个点,然后图$G$不是一个哈密顿图。这意味着在图$G+uv$中的每一个哈密顿圈都需要经过$u-v$之间的路。所以$d(u) + d(v) \geq n$,$G$必然为哈密顿图,矛盾。

这意味着,我们在研究哈密顿性质是否存在的时候,可以先将图扩展到一个边数尽可能多的情况,因为他们是相互等价的。


一个图闭包(closure)的生成:

图$G$的闭包$C(G)$是:在图$G$中满足$d(u) + d(v) \geq n$且不相邻的一对节点$u,v$之间加入一条边,递归地重复上述过程,直到不存在满足要求的点对。


有关闭包的一些结论

定理:一个图的闭包是良定义的(按照不同的顺序递归生成结果一致)

定理:一个图是哈密顿图当且仅当它的闭包也是哈密顿图。

推论:一个阶数至少为3的图$G$,如果它的闭包$C(G)$是完全图,那么$G$是哈密顿图。


证明:

假设,该定理不成立。对于$C(G)$中的所有不相邻的节点,让$u,w$是一对度数和最大的节点。
显然$d_{C(G)}(u)+d_{C(G)}(v) \leq n-1$,我们不妨令u为度数较小的那个点。
令$d_{C(G)}(u) = j$,那么$j\leq \frac{n-1}{2}$,并且有$$d_{C(G)}(w) \leq n-j-1$$令$W$为所有不与$w$所相邻的点的集合,因此$u \in W$。观察到如果$v\in W$,那么就会有$d_{C(G)}(v)\leq j$,否则的话$$d_{C(G)}(v)+d_{C(G)}(w) > d_{C(G)}(u) + d_{C(G)}(w)$$这会导致与点$u$的定义相矛盾。
因此,集合$W$中每个节点的度数均至多为$j$。因为在假设中,$|W|\leq j-1$,因此
$$d_{C(G)}(w) \geq (n-1)-(j-1) = n-j$$ 矛盾!


定理2:

这篇文章主要用于介绍$Akra-Bazzi$定理,以便于熟练应用。至于证明部分,本文就展示一个最简单的归纳法证明

使用到的材料:

论文:On the Solution of Linear Recurrence Equations
wiki

正文:

在算法导论中,我们很快就会学到一种很快很无敌的时间复杂度计算方式,就是主定理(Master Theorem)
对于任意一个算法的递推式:
$$T(n) = aT(\frac{n}{b}) + f(n)$$
通过主定理,我们可以很快的得到它的时间复杂度
1: If for some $\epsilon$, $ f(n) = O(n^{\log_b{a-\epsilon
}})$, then $T(n) = \Theta(n^{\log_ba})$
2: If $f(n) = \Theta(n^{\log_ba})$, then $T(n) = \Theta(n^{\log_ba}\lg n)$
3: If for some $\epsilon$, $f(n) = \Omega(n^{\log_ba})$, then $T(n) = \Theta(f(n))$
说人话就是你看$n^{\log_ba}$和$f(n)$谁大谁小,谁大就是谁,如果一样大就再乘个$\lg n$
推导不难,直接画递推树就能整出来。
这跟$Akra-Bazzi定理$有什么关系呢?其实就是,这个神犇在学主定理的时候,觉得这玩意可以推的更细致一些,于是他就发明了$Akra-Bazzi定理$,这个定理主要用于计算更加精确的$\Theta$复杂度
下面就是$Akra-Bazzi$定理:
对于递推式:
$$T(x) = g(x) + \sum_{i=1}^{k}a_iT(b_ix+h_i(x))$$
如果满足以下条件:(看起来很多,实际上没啥要求)

  1. 有足够大的下界
  2. $a_i$和$b_i$是关于i的常数
  3. $\forall i,\ a_i>0, 0<b_i<1$
  4. $|g’(x)| \in O(x^c)$
  5. $|h_i(x)| \in O(\frac{x^2}{(\log x)^2})$
  6. $x_0$是一个常数

就有:
$$T(x) \in \Theta(x^p(\int_1^x\frac{g(u)}{u^{p+1}}du))$$

如果把我的一生中度过的所有年集中在一起,评一下每一年的精彩程度,无论如何2022都必须保持在前三的位置。

没的可说,这一年实在是太充实了。


简单概括一下

从上半年紧张刺激的高三生活开始,五一劳动节突然的封校转线上,到6月7日如期而至的高考,然后出成绩,学车,暑假和同学租别墅狂欢,玩剧本杀,9月第一次来到南京,第一次离家这么久,来到南京大学,在一个我比较喜欢的专业。透支了自己的社交能力,认识了几个关系还不错的新朋友,直到疫情的放开,大一上学期戛然而止,回家感染新冠,虚弱了两周,2022就此结束。


放几张图片,浅浅的记录一下吧

(图片越放越多,根本停不下来)

最后高三动员的时候,发的小礼盒。
无知时诋毁郝校,成熟时理解郝校,可惜,懂事后郝校没了。
avatar

高考前的jh
avatar
avatar

我住了整整6年的宿舍
avatar

高考考场
avatar

趁着录取结果出来之前,租个大别墅,哥几个赶紧好好玩一把。
avatar

金榜提名时,可惜没有洞房花烛夜

avatar

同乡会真的是个很神奇的东西,至少让我在开学前体验到了奢华的南京大饭店。

avatar

相当曲折的考驾照经历,还好有惊无险拿到了驾照。

avatar

初中顶级好兄弟,能聚一起真的不容易。

avatar

然后是南京部分

在玄武湖拍的一张照片,一览南京市中心的高楼大厦。

avatar

到达南大最高城,北大楼!

avatar

在宿舍吃点小烧烤,喝点小酒真的是一件非常享受的事情。

avatar

联谊活动神中神!

avatar

新生杯!可惜我没上场

avatar

当了一个学期的心理委员,我还挺喜欢这个职位的,没那么多活,但也能负责一些有意思的活动,比如晚安短信。

avatar

就放着十二张吧,虽然我还想放很多图片,但放多了就没意思了,哈哈。

24小时紧急联系热线

全国心理危机干预热线

010-82951332

江苏省心理危机干预热线

025-83712977

江苏省大学生心理热线

025-58255200

其他热线

某位心理委员(cyh)

QQ号:2574092944

南大师生心理支持

QQ号:2225806137

南大倾诉邮箱

njuxlzx@163.com

鼓楼校区心理咨询室

地 址:鼓楼校区南园21舍202
预约电话:83597219
预约时间:周一至周五8:00-12:00、13:30-21:30

仙林校区心理咨询室

地 址:仙林校区敬文大学生活动中心10层
预约电话:89680355
预约时间:周一至周五8:00-12:00、13:00-21:00
(办公室电话:89681591)

给mh同学写了一个压箱底的笑话,希望她看到后可以开心

两头牛在河边吃草,

一头牛问另一头牛:
哥们,我这艹贼好吃,巧克力味的
你吃的艹是什么口味的?

牛A很高冷,淡淡地说:草莓味

牛B感觉很新奇,我焯,从小到大从来没吃过草莓味的草
“哥们,我过来尝尝”牛B说。

牛B跋山涉水来到了河对岸

吃了一口,味同嚼蜡,难吃的要死
牛B当场就怒了:你不是说了这是草莓味的,这是什么垃圾!

牛A不解:草确实没味啊

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment